package com.test;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Stream;

public class CodeExample {
    public static void main(String[] args) {
        dynamicProgramming("a");
    }
    public void test1(){
        //输入包括两个正整数a,b(1 <= a, b <= 10^9),输入数据包括多组。
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){
                int a = sc.nextInt();
                int b = sc.nextInt();
                System.out.println(a + b);
            }
    }
    public void test2(){
//        输入第一行包括一个数据组数t(1 <= t <= 100)
//        接下来每行包括两个正整数a,b(1 <= a, b <= 10^9)
        Scanner s = new Scanner(System.in);
        int lineNumber = s.nextInt();
        for (int i = 0; i < lineNumber; i++) {
            int a = s.nextInt();
            int b = s.nextInt();
            System.out.println(a + b);
        }
    }

    public void test3() {
        //输入包括两个正整数a,b(1 <= a, b <= 10^9),输入数据有多组, 如果输入为0 0则结束输入
        Scanner s = new Scanner(System.in);
        while (s.hasNext()) {
            int a = s.nextInt();
            int b = s.nextInt();
            if (a == 0 || b == 0) {
                break;
            }
            System.out.println(a + b);
        }

    }
        public void test4(){
        //输入数据包括多组。
            //每组数据一行,每行的第一个整数为整数的个数n(1 <= n <= 100), n为0的时候结束输入。
            //接下来n个正整数,即需要求和的每个正整数。
            Scanner s = new Scanner(System.in);
            ArrayList<Integer> ai = new ArrayList<>();
            for (; s.hasNext(); ) {
                int n = s.nextInt();
                if (n == 0) {
                    break;
                }else {
                    int sum = 0;
                    for (int i = 0; i < n; i++) {
                        sum += s.nextInt();
                    }
                    ai.add(sum);
                }
            }
            for (int i : ai) {
                System.out.println(i);
            }
        }


        public void test6(){
        //输入的第一行包括一个正整数t(1 <= t <= 100), 表示数据组数。
            //接下来t行, 每行一组数据。
            //每行的第一个整数为整数的个数n(1 <= n <= 100)。
            //接下来n个正整数, 即需要求和的每个正整数。
//        import java.util.*;
//            public class Main {
//                public static void main(String[] args) {
                    Scanner s = new Scanner(System.in);
                    ArrayList<Integer> ai = new ArrayList<>();
                    int raw = s.nextInt();
                    while(raw>0){
                        for (; s.hasNext(); ) {
                            int n = s.nextInt();
                            if (n == 0) {
                                break;
                            }else {
                                int sum = 0;
                                for (int i = 0; i < n; i++) {
                                    sum += s.nextInt();
                                }
                                ai.add(sum);
                            }
                        }
                        raw--;
                    }
                    for (int i : ai) {
                        System.out.println(i);
                    }
                }
//            }

//        }

    public void test7(){
        //输入数据有多组, 每行表示一组输入数据。
        //每行的第一个整数为整数的个数n(1 <= n <= 100)。
        //接下来n个正整数, 即需要求和的每个正整数。
        Scanner s = new Scanner(System.in);
        ArrayList<Integer> ai = new ArrayList<>();
        int raw = s.nextInt();
            for (; s.hasNext(); ) {
                int n = s.nextInt();
                if (n == 0) {
                    break;
                }else {
                    int sum = 0;
                    for (int i = 0; i < n; i++) {
                        sum += s.nextInt();
                    }
                    ai.add(sum);
                }
            }
        for (int i : ai) {
            System.out.println(i);
        }
    }


    public void test9(){
        //输入数据有多组, 每行表示一组输入数据。
        //每行不定有n个整数，空格隔开。(1 <= n <= 100)。
//        import java.util.*;
//        public class Main {
//            public static void main(String[] args) {
                Scanner s = new Scanner(System.in);
                ArrayList<Integer> ai = new ArrayList<>();

                for(;s.hasNext();){
                    String[] num = s.nextLine().split(" ");
                    int sum = 0;
                    for(int i=0;i<num.length;i++){

                        sum+=Integer.valueOf(num[i]);
                    }
                    ai.add(sum);
                }
                for (int i : ai) {
                    System.out.println(i);
                }
//            }
//        }
    }

    @Test
    public void haha(){
        Scanner sc = new Scanner(System.in);
        //多个测试用例，每个测试用例一行。
        //每行通过空格隔开，有n个字符，n＜100
        //对于每组测试用例，输出一行排序过的字符串，每个字符串通过空格隔开
        while(sc.hasNext()){
            String s = sc.nextLine();
            String [] ss = s.split(" ");
            Arrays.sort(ss);
            System.out.println(String.join(" ",ss));
        }
    }
    @Test
    public void haha2(){
        Scanner sc = new Scanner(System.in);
        //多个测试用例，每个测试用例一行。
        //每行通过,隔开，有n个字符，n＜100
        //对于每组用例输出一行排序后的字符串，用','隔开，无结尾空格
        while(sc.hasNext()){
            String s = sc.nextLine();
            String [] ss = s.split(",");
            Arrays.sort(ss);
            System.out.println(String.join(" ",ss));
        }
    }

    @Test
    public void haha3(){
        //输入有多组测试用例，每组空格隔开两个整数,对于每组数据输出一行两个整数的和
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            System.out.println(sc.nextLong() + sc.nextLong());
        }
    }

    //  动态规划核心思想：将问题分解化，引用之前的结果做参考来计算当前的结果
    public static void dynamicProgramming(String s1){
        String s = "abcba";
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int l = 0; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                // 单个字符是回文
                if (l == 0) {
                    dp[i][j] = true;
                // 两个字符相等是回文
                } else if (l == 1) {
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    // s.charAt(i) 表示最前面的字符  ，s.charAt(j)，
                    // 字串是回文且两端相等是回文
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);//  父串是回文则子串(前后减一)也是回文
                }
                // dp[i][j] 为true时表示是个回文串， L 相当于字符串的长度，也可以理解为i到j的步长。
                if (dp[i][j] && l + 1 > ans.length()) { // 加法优先级要大于比较'>'的优先级
                    ans = s.substring(i, i + l + 1);
                }
            }
        }
        for(int i = 0; i<n; i++){
            for(int j=0; j<n;j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println(ans);
//        return ans;
    }

    @Test
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }


}

class TreeNode{
        String val;
    TreeNode left;
    TreeNode right;
    }

